#include <bits/stdc++.h>
using namespace std;

/*
2071. 你可以安排的最多任务数目
已解答
困难
相关标签
相关企业
提示
给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。

给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。

 

示例 1：

输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）
示例 2：

输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）
示例 3：

输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）
示例 4：

输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）
 

提示：

n == tasks.length
m == workers.length
1 <= n, m <= 5 * 104
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 109
*/

// 法一
// 贪心 + 二分查找
class Solution {
	private:
	// 判断能否完成 k 个任务的辅助函数
	bool canComplete(vector<int>& tasks, vector<int>& workers, int pills, int strength, int k) {
		if (k == 0)  return true;  // 如果没有任务需要完成，返回 true
		if (k > workers.size())     return false;  // 如果任务数量大于工人数量，返回 false

		// 使用 multiset 来存储工人的力量值，确保工人按顺序分配任务
		multiset<int> workerSet(workers.begin(), workers.end());
		int usedPills = 0;  // 记录已经使用的药丸数量

		// 遍历每个任务，尝试分配给工人
		for (int i = k - 1; i >= 0; --i) {
			// 查找一个力量足够的工人来完成任务
			auto it = workerSet.lower_bound(tasks[i]);
			if (it != workerSet.end())  {
				workerSet.erase(it);  // 如果找到了工人，移除该工人
			} else {
				// 如果没有足够力量的工人，检查是否能用药丸增强工人的力量
				if (usedPills >= pills) return false;  // 如果药丸用完，返回 false
				// 尝试找一个工人，他的力量经过药丸增强后可以完成任务
				it = workerSet.lower_bound(tasks[i] - strength);
				if (it == workerSet.end())  return false;  // 如果没有这样的工人，返回 false
				workerSet.erase(it);  // 移除增强后的工人
				usedPills++;  // 使用一个药丸
			}
		}
		return true;  // 如果完成了 k 个任务，返回 true
	}

public:
	// 返回能完成的最多任务数
	int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
		// 对任务和工人力量进行排序，便于使用贪心策略
		sort(tasks.begin(), tasks.end());
		sort(workers.begin(), workers.end());
		// 使用二分查找来确定最多能完成多少个任务
		int left = 0, right = min(tasks.size(), workers.size());
		int ans = 0;
		// 二分查找，left 为最小任务数，right 为最大任务数
		while (left <= right) {
			int mid = left + (right - left) / 2;  // 计算当前的中间值
			// 检查是否可以完成 mid 个任务
			if (canComplete(tasks, workers, pills, strength, mid)) {
				ans = mid;  // 如果可以完成，更新答案
				left = mid + 1;  // 尝试完成更多任务
			} else {
				right = mid - 1;  // 否则，尝试完成更少的任务
			}
		}
		return ans;  // 返回最多能完成的任务数
	}
};

// 添加一个模拟队列
// 法二
int que[50010]; // 队列，用于存储工人的索引

class Solution {
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        // 获取任务和工人的数量
        int tasks_size = tasks.size();
        int workers_size = workers.size();
        // 对任务和工人力量进行排序，方便后续的分配
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        // 定义一个检查函数，检查是否可以完成 mid 个任务
        auto check = [&](int mid) -> bool {
            int head = 0, tail = -1, p = pills; // head 和 tail 用于模拟队列，p 为剩余的药丸数
            // i 是任务的索引，j 是工人的索引
            for (int i = mid - 1, j = workers_size - 1; i >= 0; --i) {
                // 如果队列为空，则从工人中获取一个工人
                if (tail < head)        que[++tail] = j--;
                // 检查当前工人是否能完成任务
                if (tasks[i] > workers[que[head]]) {
                    // 如果当前工人力量不足，且没有药丸增强，返回 false
                    if (p == 0 || workers[que[head]] + strength < tasks[i])
                        return false;
                    // 尝试使用药丸增强工人的力量，找到合适的工人
                    while (j >= 0 && strength + workers[j] >= tasks[i])
                        que[++tail] = j--;
                    // 如果队列有可用工人，使用药丸并移除工人
                    if (tail >= head) {
                        --p;
                        --tail;
                    }
                } else {
                    // 如果当前工人的力量足够，直接分配任务，移除该工人
                    ++head;
                }
            }
            // 如果所有任务都能分配，返回 true
            return true;
        };
        // 二分查找最大能完成的任务数
        int left = 1, right = min(tasks_size, workers_size);
        int result = 0, mid = 0;
        // 二分查找任务数
        while (left <= right) {
            mid = (left + right) / 2; // 中间值为当前尝试完成的任务数
            if (check(mid)) {
                result = mid; // 如果能完成 mid 个任务，更新结果并尝试更多任务
                left = mid + 1;
            } else {
                // 否则，尝试完成更少的任务
                right = mid - 1;
            }
        }

        // 返回能完成的最大任务数
        return result;
    }
};

	